The present invention relates to a method of routing telephone or data calls in modern telecommunication networks, especially under high traffic load conditions.
It is becoming more and more complicated to manage telecommunication networks in today""s communication environment due to the growing traffic load. One of the complex tasks of networks management is routing calls having different priorities.
Generally, a telecommunication network such as a TDM based telephone network may be represented as comprising nodes and links. Each node constitutes a transfer point that is typically a network element (NE), for example a Digital Cross Connect device. The links are made up of carrier lines, such as E1/T1 lines for transmitting telephone calls say, from a local exchange to an access network. Routing paths between nodes are typically set up in advance and do not change dynamically. In the telephone network, calls addressed to a destination node are simply assigned to the path that connects the ingress node to the egress node and comprises a number of links.
There are known algorithms for setting up the shortest path between two nodes i.e., the algorithms attempting to allocate the network resources efficiently. One of such algorithms is the Dijkstra""s algorithm, which can be used to find the shortest path between any two nodes in a particular system. Such algorithms usually allow for a single weighing factor for each link between the nodes, which factor is typically used to compare relative costs of different transmission links. Mathematically, the so-called xe2x80x9cshortest path algorithmsxe2x80x9d use representations of the network as a graph in which nodes are called xe2x80x9cverticesxe2x80x9d and links (direct connections between two vertices) are called xe2x80x9cedgesxe2x80x9d.
It should be noted that, the traffic in the modern telecommunication networks is typically of different priority levels, which fact is not taken into account in the above-mentioned xe2x80x9cshortest path algorithmsxe2x80x9d.
A common situation which usually takes place in telecommunication networks today is the following: a new call having a particular priority arrives and should be routed through the network, while the network is fully loaded with calls having various priorities. Actually, the problem arises when at least a portion of the network, required for a routine routing, appears to be busy. A similar situation may be raised when one of the links of the system fails and its traffic needs to be rerouted. The goal would be to allocate the new demand using the available resources, or in case there is no enough resourcesxe2x80x94to insert the new call by dropping some traffic.
Different approaches exist of how to define criteria of dropping the traffic in such cases and how to perform the above task based on the criteria defined.
All the traffic is usually divided into streams having different priorities, and each call usually has an associated priority. Every link of the network can be given a current link priority selected according to the traffic passing through the link.
For example, all lower priority links can be selected to form a pool of available links to be processed by the Djiaekstra algorithm. The algorithm will then find the shortest path, and the links forming the shortest path will be reassigned for the new demand (i.e. the existing lower priority traffic will be dropped and the links will handle the higher priority traffic). This can be done per one priority level at a time until a satisfactory solution is found. The method suffers form a number of disadvantages: firstly, it is multistage and secondly- it is far from optimum because of the criteria chosen, i.e., the priorities are taken into account in a straight-forward way. In other words, if a very convoluted path consisting of many low priority links is found, the algorithm will block all these links irrespective of the number of paths involved. However, there might be a solution that blocks few links of a slightly higher priorityxe2x80x94but this solution will not be revealed.
It is therefore the purpose of the present invention to provide a method allowing optimization of routing and rerouting in a network with traffic characterized by various priorities.
Continuing the topic concerning the criteria of dropping part of existing traffic for embedding a new demand in the network, there have been proposed the following three criteria (in the order of decreasing importance). The criteria are formulated for ensuring the result with producing the smallest perturbation to the network having a number of links:
1. Disable call paths (which are also named calls or connections) with the lowest priority first;
2. Disconnect the smallest number of call paths;
3. Chose the shortest path in the network using links which can be freed from calls according to criteria (1) and (2).
In other words, in the ideal situation, it would be desired to only abandon or block traffic of the lowest priority and at minimal number of paths (i.e. minimal number of calls) and links.
In order to take into account all these criteria in the process of routing one or more calls in a telecommunication network, a new method has been proposed by the Inventors.
The new approach is based on applying an algorithm of finding optimal path(s) to an augmented graph built for a telecommunication network, wherein all edges of the augmented graph are weighed to reflect priority of telecommunication traffic presently taking place there-through.
The calls mentioned above (both those forming the telecommunication traffic, and the new ones) should be considered any of the known types of telecommunication transmission including voice, fax, data, etc.
It should be explained that any telecommunication network comprises a plurality of network elements and a plurality of physical connections each bridging a pair of the network elements. A conventional network may be represented as a connected network graph comprising nodes and links, wherein the nodes respectively correspond to the network elements, while the links interconnect said nodes and respectively correspond to the connections physically existing between the network elements of the network.
The augmented graph, in the frame of the present application, should be understood as a graph built on the basis of the network graph having nodes and real links, by adding to it virtual links; both real and virtual links being considered edges of the augmented graph. The maximal form of the augmented graph is a complete graph where each two nodes are connected by an edge. While weights of the real links reflect real telecommunication traffic presently taking place there-through, weights of the virtual links in the augmented graph are to reflect virtual telecommunication traffic (for purposes which will become apparent from the following description).
In other words, the method of routing calls having priorities in a telecommunication network comprises the following steps:
building an augmented graph of the network, the augmented graph comprising nodes and edges;
weighing each edge of the augmented graph to reflect the priority of calls presently taking place there-through;
obtaining one or more new calls, each defined by end-point nodes and a particular priority;
applying a pathfinder optimization algorithm to the augmented graph to determine an optimal pathfinder solution, having the minimal total weight, for routing said one or more new calls in the augmented graph (in other words, determining optimal path(s));
if said optimal pathfinder solution is determined, allocating corresponding to it links in the network graph for routing the one or more new calls in the telecommunication network;
providing for placing said one or more new calls via the allocated links by ensuring that, if necessary, call(s) having lower priorities and currently held by the allocated links be dropped therefrom, updating the augmented graph on changes whenever take place in the network, and
returning to the step of obtaining one or more new calls.
The above-mentioned changes, which may take place in the network, may include at least one, selected from the following non-exhaustive list comprising:
adding said one or more new calls routed via one or more links,
dropping said one or more of previously held calls due to placing said one or more new calls (both adding and dropping calls alters priorities and weights of the edges),
terminating currently existing calls (which will turn priorities of the corresponding edges to xe2x80x9c0xe2x80x9d as will be explained below),
a failure in the network, such as a link or node outage which causes distortion in the graph and requires rerouting of thus dropped calls,
reconsidering the length parameter of the links (which may also alter weights of the edges, as will be explained below).
Naturally, calls that are to be rerouted due to failure of any network element such as a link, a port or even an entire node may be considered to be new calls, and processed according to the method.
In the most preferred version of the method, the step of building the augmented graph includes building of an optimal augmented graph by
defining chains of nodes (call paths) respectively used by each of the calls currently taking place in the network, and
converting said chains into complete sub-graphs, wherein each two nodes of any of said complete sub-graphs are connected with an edge. Preferably, the weighting is performed to also reflect a so-called length parameter of the edges. In a real network, the length parameter may be a function of at least one argument associated with a link, for example of distance, tariff, administrative cost, etc.
The inventive approach can be applied both to cases where one new call is routed at a time, and to those where a plurality of new calls are simultaneously routed. For example, in the latter case, the pathfinder optimization algorithm is a multi-commodity algorithm.
However, for the sake of simplicity, the following description will preferably refer to the method dealing with one new call at a time.
In this case, the pathfinder optimization algorithm constitutes a shortest path algorithm, and the optimal solution is the shortest path between said end-point nodes, said shortest path comprising one or more edges and being characterized by the minimal weight and the priority lower than that of the new call.
Weight of the shortest path is a sum of weights of the component edges. Rules of defining weights of edges in the augmented graph will become apparent from the description, which follows below. Priority of the shortest path in the augmented graph is considered to be the maximal among the priorities based on which the weights of the component edges have been calculated. In other words, the priority of any of the edges and, consequently, of the network links forming the shortest path should be lower than the priority of the new call. The physical meaning of such a condition is that a new call, which might only be placed in the network by dropping one or more calls having the same priority, should be dropped itself.
Empirically, the advantages of the method may be explained as follows: when constructing the augmented graph based on the physical links associated with xe2x80x9cpriority and lengthxe2x80x9d weights, edges of the augmented graph will bear full information on the current traffic priorities via various possible paths through the graph. When seeking for the optimal pathfinder solution (e.g., the shortest path) on the augmented graph, such information enables obtaining a single-stage universal solution which will take into account and minimize both the priorities of the calls currently participating in the shortest path, and the physical length of the shortest path. The only thing remaining to do is converting the obtained solution into a real path in the existing network""s graph.
Preferably, in the method, the lower priorities are designated with smaller numbers, and the absence of traffic is designated with the smallest number (for example, the xe2x80x9c0xe2x80x9d priority i.e., the edge is available for routing a new call). According to such logic, the less intensive and less significant the traffic via an edge, the smaller the priority and weight of the edge. It also should be kept in mind that real links may be capable of conducting more than one call at a time, say, by using a multiplexing technology. Capacity C of a real link is equal to the number of calls the link is able to hold simultaneously. If capacity of a real link is not saturated (i.e., one or more calls still may be routed there-through), the priority of the edge corresponding to the link is considered to be xe2x80x9c0xe2x80x9d.
In the circumstances when the network is not fully loaded, the above-proposed method will successfully perform the conventional routing by simply finding a path consisting of edges where the priorities are designated as xe2x80x9c0xe2x80x9d. It is understood, that the allocated physical path in the network will serve as the final result of the routing, since the new call can just be passed through the available path without any problems, i.e., without dropping any calls.
In case the network is loaded (i.e. no path with xe2x80x9c0xe2x80x9d priority can be found for a new call (as well as in case any link in the loaded network fails and its traffic should be rerouted via the remaining links), the determined shortest path should be considered the one its traffic to be dropped for placing the new call.
In order to describe the inventive method in greater detail, the particular steps will be further explained.
Preferably, step a) of building the augmented graph includes the following operations:
building a complete sub-graph for each call path by adding virtual links in order to connect all the node pairs belonging to the same call path and not connected by real links. That is, if we have a call path composed by H nodes, we have to add at most xe2x85x9[(2H xe2x88x923)2xe2x88x921] links, since there exist at least (Hxe2x88x921) real links among the xc2xd H (Hxe2x88x921) possible node pairs. In other words,
xc2xd H (Hxe2x88x921)xe2x88x92(Hxe2x88x921)=xe2x85x9[(2H xe2x88x923)2xe2x88x921]
The step b) of assigning weights to the edges of the augmented graph can generally be described as determining a current weight W to each edge (whether the link or the virtual link, connecting nodes xe2x80x9cxxe2x80x9d and xe2x80x9cyxe2x80x9d), wherein the current weight being considered the minimal weight among component weights of calls passing through the edge; each of the component weights being a function of the respective traffic priority P and the length parameter L of the edge:
Wxy=min {WxyC},
WxyC=k*PC+LxyC;
where:
Cxe2x80x94labels the number of calls passing through the edge (either virtual or physical) between nodes x and y,
WxyCxe2x80x94designates a component weight of a call C over edge x,y,
PCxe2x80x94indicates the priority of a call C, and
LxyCxe2x80x94designates the value of length parameter (say, in hops or cost) between nodes xe2x80x9cxxe2x80x9d and xe2x80x9cyxe2x80x9d, along the path formed by the call C.
kxe2x80x94is a coefficient, preferably for reflecting rules of managing calls with different priorities in the particular network; maximal value of xe2x80x9ckxe2x80x9d reflects the maximal number of possible calls of priority P in the network.
In particular cases, the step (b) may be accomplished in the following order:
(i)xe2x80x94assigning a current weight W to an edge being a real link between nodes x, y by selecting a minimal weight among weights respectively calculated for all real and possible calls via said link according to its capacity C and the following formula:
xe2x80x83W(x,y)=min {W(x,y)call 1, W(x,y)call2, . . . W(x,y)call C},
or
W(x,y)=min{(k*Pcall 1+L),{(k*Pcall2+L), . . . {(k*Pcall C+L)};
and where:
Pcall ixe2x80x94is the priority of a particular call (call 1, call2, . . . or call C) currently taking place (or possible) via the link which forms the edge between the nodes x,y. If call xe2x80x9cixe2x89xa6Cxe2x80x9d does not exist, its priority will be considered xe2x80x9c0xe2x80x9d.
Lxe2x80x94is the length parameter being a function of number h of real links (hops) physically existing between the nodes x,y; (optionally, the length parameter L can also be a function of the edge dimensions d, price s, quality q and other administrative parameters, so that L=f(h, d, s, q . . . ); in the simplest case where no other parameters are considered for a real link being one hop, L=1;
kxe2x80x94as above, is the coefficient preferably reflecting the maximal number of possible calls of priority P in the network, i.e., the total number of node pairs that can be formed, and therefore the maximal number of edges that the network may contain: kmax=xc2xd N(Nxe2x88x921), where N is the number of nodes in the network. The coefficient is selected to be rather high to put the major emphasize on the criterion of the traffic priorities. It should be mentioned, however, that the coefficient k may reflect rules which are empirically set for a particular network. For example, the value of xe2x80x9ckxe2x80x9d may take into account an arbitrary consideration that instead of dropping more than five calls with priority xe2x80x9c5xe2x80x9d it is preferable to drop up to three calls with higher priority xe2x80x9c6xe2x80x9d;
(ii)xe2x80x94assigning a current weight W to an edge being a virtual link between nodes x, y by selecting a minimal weight among weights respectively calculated for all xe2x80x9cnxe2x80x9d real calls which continuously pass between nodes x, y via groups of real links enveloping the virtual link:
W(x,y)=min {W(x,y)call 1, W(x,y)call 2, . . . W(x,y)call n},
or
xe2x80x83W(x,y)=min{(k*Pcall 1+Lcall 1), {(k*Pcall2+Lcall2), . . . {(k*Pcall n+Lcall n)};
and where:
Pcall ixe2x80x94is the priority of a particular call (call i) currently taking place via a group of real links enveloping the virtual edge between the nodes x,y.
Lcall ixe2x80x94is the edge length parameter, being a function of number h of real links (hops) physically present in a particular group of links between the nodes x,y via which call i passes; in the simplest case, L=h;
kxe2x80x94as above, reflects the importance of the priority criterion. It can be selected as described above, keeping in mind that kmax=xc2xd N(Nxe2x88x921).
Further, step c) of the method (determining the optimal path(s)) can be accomplished as follows:
i) in the basic case where one new call enters the network at a timexe2x80x94by applying any of the known xe2x80x9cshortest pathxe2x80x9d algorithms to determine a path between two end-points s,t, of the new call, which would have the minimal weight:             W              s        ,        t              =          min      ⁡              (                              Σ            s            t                    ⁢                      W                          x              ,              y                                      )              ;
xe2x80x83ii) in a general case, where a plurality of new calls enter the networkxe2x80x94by applying to the augmented graph a multi-commodity algorithm for determining a respective plurality of paths for the plurality of new calls such that the determined paths have the minimal total weight.
In other words, for the general case the method requires to: minimize             Σ      ij        ⁢          f      ij        ⁢          W      ij        ,
subject to the following flow constraint equation:                     Σ        j            ⁢              f        ij              +                  Σ        j            ⁢              f        ji              =      {                                                      Σ              s                        ⁢                          d              st                                                                          if              ⁢                              xe2x80x83                            ⁢              i                        =            t                                                                          Σ              t                        -                          d              st                                                                          if              ⁢                              xe2x80x83                            ⁢              i                        =            s                                                0                          otherwise                    
where                               Σ          ij                ⁢                  :                                              sum          ⁢                      xe2x80x83                    ⁢          of          ⁢                      xe2x80x83                    ⁢          all          ⁢                      xe2x80x83                    ⁢          links          ⁢                      xe2x80x83                    ⁢          over          ⁢                      xe2x80x83                    ⁢          the          ⁢                      xe2x80x83                    ⁢          augmented          ⁢                      xe2x80x83                    ⁢          graph                ;                                          f          ij                ⁢                  :                                                          a            ⁢                          xe2x80x83                        ⁢            flow            ⁢                          xe2x80x83                        ⁢            between            ⁢                          xe2x80x83                        ⁢            node            ⁢                          xe2x80x83                        ⁢            i            ⁢                          xe2x80x83                        ⁢            and            ⁢                          xe2x80x83                        ⁢            node            ⁢                          xe2x80x83                        ⁢            j                    ,                      i            .            e            .                          ⁢                  xe2x80x83                                        xe2x80x83                                      calls          ⁢                      xe2x80x83                    ⁢          which          ⁢                      xe2x80x83                    ⁢          enter          ⁢                      xe2x80x83                    ⁢          or          ⁢                      xe2x80x83                    ⁢          leave          ⁢                      xe2x80x83                    ⁢          node          ⁢                      xe2x80x83                    ⁢          i                ;                                          W          ij                ⁢                  :                                    weight        ⁢                  xe2x80x83                ⁢        of        ⁢                  xe2x80x83                ⁢        the        ⁢                  xe2x80x83                ⁢        link        ⁢                  xe2x80x83                ⁢        i        ⁢                  -                ⁢        j                                          Σ          j                ⁢                  f          ij                ⁢                  :                                              flows          ⁢                      xe2x80x83                    ⁢                      (            calls            )                    ⁢                      xe2x80x83                    ⁢          entering          ⁢                      xe2x80x83                    ⁢          node          ⁢                      xe2x80x83                    ⁢          i                ;                                          Σ          j                ⁢                  f          ji                ⁢                  :                                              flows          ⁢                      xe2x80x83                    ⁢                      (            calls            )                    ⁢                      xe2x80x83                    ⁢          outgoing          ⁢                      xe2x80x83                    ⁢          node          ⁢                      xe2x80x83                    ⁢          i                ;                                s        ⁢                  :                                    source        ⁢                  xe2x80x83                ⁢        node                                t        ⁢                  :                                    target        ⁢                  xe2x80x83                ⁢        node                                          d          st                ⁢                  :                                    number        ⁢                  xe2x80x83                ⁢        of        ⁢                  xe2x80x83                ⁢        calls        ⁢                  xe2x80x83                ⁢        between        ⁢                  xe2x80x83                ⁢        node        ⁢                  xe2x80x83                ⁢        s        ⁢                  xe2x80x83                ⁢        and        ⁢                  xe2x80x83                ⁢        t            
As a result, one of the following values is obtained for each link in the augmented graph:
fij=1 if the link (i,j) is a part of a path for one of the new calls, and =0 if the link (i,j) is not a part of such a path.
Returning to the most illustrative basic case, when the condition       W          s      ,      t        =      min    ⁡          (                        Σ          s          t                ⁢                  W          xy                    )      
is used in the shortest path algorithm, one can see that the criteria stated for the novel method are satisfied. Keeping in mind that Wxy=min {WxyC}, and WxyC=k*PC+LxyC, one can see that the minimal path is selected by firstly trying to satisfy the major criterion of minimal priority by selecting the path where edges bear calls with possibly lowest priorities and in any case lower than the priority of the new call. Secondly, in case there exist a number of the paths equally satisfying the major criterion, the length criterion is applied, i.e. the path having the minimal length will be chosen from the selected paths, i.e. the method will produce the minimal perturbation to the network.
As has been mentioned, the augmented graph, once built, is automatically updated when priorities of the traffic change, or physical links or nodes (network elements) fail. It should be emphasized however, that it must not be built from the very beginning for each new incoming call. It is another advantage of the method, that the network represented as the augmented graph becomes solvable and easily updateable.